The invention concerns an associative memory (or content addressable memory CAM!) architecture supporting various comparative tests as well as operations on variable-length words.
Such a memory can be used in the majority of computer fields where the responses sought are the result of comparisons between a search argument and a set of words contained in the associative memory. More particularly, the present invention applies to the processing of databases (for example, in relational algebra operations), in the execution of artificial intelligence languages (clause filtering in PROLOG, evaluation of function invocation in LISP, and method searches in object languages), and in highspeed FFDI local fiber-optic networks (address filtering, bridges and repeaters).
Associative memories are generally viewed as effective means for significantly improving the performance of computers running specific applications requiring excessive calculation times.
In effect, an associative memory is a data-storage mechanism in which the data-search occurs directly in the memory contents and not in the addresses of the data stored in the memory.
The architectures of known associative memories generally vary as a function of the applications utilized. The associative memory used for Data Flow calculators (made by the Japanese company Matsushita Electrical Industrial) is described in an article by Hiroshi Kadota et al., entitled "An 8-Kbit Content-addressable and Reentrant Memory", published in the IEEE Journal of Solid State Circuits, volume SC-20, number 5, Oct. 1988, pages 543 to 547.
Another associative memory architecture was used for the local networks (AMD, Am 99C10) described in an article entitled "Donnez-lui le mot de passe, la me/ moire se chargera de trouver l'information"("Give it the password and the memory will find the information itself") published in Electronique Hebdo, number 97, 1989, page 19.
Another kind of associative memory architecture, devoted to the processing of signals and images, is described in an article by Simon R. Jones et al. , entitled "A 9-Kbit Associative Memory for High-Speed Parallel Processing Applications", published in the IEEE Journal of Solid Stage Circuits, volume 23, number 2, Apr. 1988, pages 543 to 547.
Other associative memory architectures for specific artificial intelligence applications, neuronal networks, the processing of lists in LISP, and the rapid scanning of graphs are described in articles written by Takeshi Ogura ("A 20 Kb CMOS Associative Memory Lsi for Artificial Intelligence Application", in Proceedings of the IEEE International Conference on Computer Design (ICCD 86) pages 574 to 577) L. T. Clark and R. O. Grondin ("A Pipelined Associative Memory Implemented in VLSI", in the IEEE Journal of Solid State Circuits, volume 24, number 1, Feb. 1989, pages 28 to 34), and H. Shin and M. Malek ("A Boolean Content Addressable Memory and its Applications", in Proceedings of the IEEE, volume 73, number 6, Jun. 1985, pages 1142 to 1144).
Many other types of associative memory architectures are described in different publications. Nevertheless, all of those associative memories can only be used to run a limited number of applications.
In effect, known architectures (and, in particular, the architectures described in the abovementioned articles) are characterized by an organization (parallel, bit-series, word-series, etc.) which is dependant upon one (or possibly several) target application(s).
The advantage of the present invention is precisely that it permits the use of associative memories in a number of different applications.
The size of associative memories is limited by two sorts of parameters: economic and technical.
Limitations due to economic parameters can be mitigated by considering different organizations which require a compromise between the speed, size and cost of the memory (its cost is determined by the cost of the storage elements and that of the interconnections among memory cells).
Technical parameters are those which limit the size of a memory-word and the size of the memory itself!. More precisely, those parameters which, in the former state of the art, posed an obstacle to our ability to use associative memories in different fields of application without having to conceptualize anew the architecture of the memory for each application, were: the processing of words or of associations of variable-length words, increases in the size of the words, absence of hardware structure integrated into the memory to execute text operations other than equality, and the complex applications which derive therefrom.
The present invention overcomes the limitations due to certain of these very same technical parameters. The article entitled "A 20 kb CMOS Associative Memory LSI for Artificial Intelligence", in the Proceedings of the IEEE International Conference on Computer Design (ICCD 86), pages 574 to 577, proposes a solution to the problem of variable-length word association. In that article, the author suggests that the memory word be broken down into an "information" field, coded in 32 bits, and a "number" field, coded in 8 bits. The number field permits the numbering of words belonging to the same association. This solution is costly in terms of hardware complexity, and reduces the possibility of increasing the size of the memory's information field by integrating the processing of variable-length words into the memory map itself. While this solution solves the problem of managing variable-length words, it is not particularly appropriate for operations involving the recognition of character-strings within text.
Another solution is described by C. Stormon, M. Brule, J. Oldfield and J. C. D.F. Ribeiro in an article entitled "An Architecture Based on Content-addressable Memory for the Rapid Execution of Prolog", published in Proceedings of the Fifth International Conference and Symposium on Logic Programming, pages 1448 to 1473, Aug. 1988. This solution for resolving the problem of processing variable-length words also took into account signals emitted from a multiple response management module. In this case as well, the solution adopted is designed for the selection of clauses in PROLOG.
Yet another solution requires that all the words stored in the memory be of the same size and that the address of the beginning of each word be known before the search phase. This solution was proposed by Stuart J. Adams et al. in an article entitled "A Parallel General Purpose CAM Architecture", published in the Proceedings of the Fourth MIT Conference on Advanced Research in VLSI, pages 51 to 71, 1986.